package leetcode.day_2021_04_12_2021_04_18;

/**
 * 91. 解码方法
 * https://leetcode-cn.com/problems/decode-ways/
 * https://leetcode-cn.com/problems/decode-ways/solution/nao-tu-fen-xi-dong-tai-gui-hua-by-206663-fh5k/
 *
 * i从1开始对字符串进行遍历
 *      1、当前为‘0’只能与前一位结合
 *          1.1、 无法结合-直接返回0
 *          1.2、 可结合，可能会破坏之前解码情况如‘2102’
 *              1.2.1、 位于边界（i==1） dp[i]=dp[0]
 *              1.2.2、 不在边界 dp[i]=dp[i-2]
 *      2、当前非‘0’与前一位结合后数值
 *          2.1、处于11-26之间
 *              2.1.1、 位于边界（i==1） dp[i]=dp[0]+1
 *              2.1.2、 不在边界 dp[i]=dp[i-1]+dp[i-2]
 *          2.2、 位于11-26之外
 *              2.2.1、 解法总数不变 dp[i] = dp[i-1]
 */
public class LeetCode0091 {
    public static int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }
        int len = s.length();
        int[] dp = new int[len];
        dp[0] = 1;
        for (int i=1; i<len; i++) {
            if (s.charAt(i) == '0') {
                if (s.charAt(i-1)=='1' || s.charAt(i-1)=='2') {
                    if (i==1) {
                        dp[i] = 1;
                    } else {
                        dp[i] = dp[i-2];
                    }
                } else {
                    return 0;
                }
            } else {
                int value = 10*(s.charAt(i-1)-'0') + (s.charAt(i)-'0');
                if (value>=11 && value<=26) {
                    if (i==1) {
                        dp[i] = dp[0]+1;
                    } else {
                        dp[i] = dp[i-1] + dp[i-2];
                    }
                } else {
                    dp[i] = dp[i-1];
                }
            }
        }
        return dp[len-1];
    }

    public static void main(String[] args) {
        System.out.println(numDecodings("12"));
        System.out.println(numDecodings("226"));
        System.out.println(numDecodings("210"));
        System.out.println(numDecodings("06"));
    }
}
